/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/recover-rotated-sorted-array
   @Language: C++
   @Datetime: 16-02-09 05:15
   */

class Solution {
public:
	/** Tips: We DO NOT know the origin sorted array in ascending order
	 * step 1 : detect the origin array sorted order first
	 * If origin is ascending order, rotate it, the A[0] must >= A[end-1];
	 * vice versa.
	 * step 2 : find the rotate position i.
	 * step 3 : rotate it. (see problem 8: Rotate String)
	 * */
	void recoverRotatedSortedArray(vector<int> &A) {
		// write your code here
		// we don't know the origin sorted array in ascending order or not
		if (A.size()<3) return;
		int i;    // the rotate position
		if (A[A.size()-1] <= A[0]){
			// the origin sorted array in ascending order
			for(i=1; i<A.size() && A[i]>=A[i-1]; ++i);
			if (i>=A.size()-1 || A[i+1]<A[i]) return;
		}
		else{   // the origin sorted array in descending order
			for(i=1; i<A.size() && A[i]<=A[i-1]; ++i);
			if (i>=A.size()-1 || A[i+1]>A[i]) return;
		}
		reverse(A.begin(),A.begin()+i);
		reverse(A.begin()+i,A.end());
		reverse(A.begin(),A.end());
	}
};
